The present invention is directed generally to the transmission of signals in communications systems. More particularly, the invention relates to systems, devices, and methods for producing, transmitting, receiving, and decoding forward error corrected signals using multi-dimensional irregular array codes and using the codes to correct errors in signal.
The development of digital technology provided the ability to store and process vast amounts of information. While this development greatly increased information processing capabilities, it was soon recognized that in order to make effective use of information resources it was necessary to interconnect and allow communication between information resources. Efficient access to information resources requires the continued development of information transmission systems to facilitate the sharing of information between resources.
One way to more efficiently transmit large amounts of information is through forward error correction (FEC) coding. FEC coding can result in a processing gain that allows for lower signal power and/or higher data rates while achieving a required data error rate. FEC coding is the addition of redundancy to transmitted data to provide the ability to detect and correct errors that occur during data transmission.
FIG. 1 shows the structure of FEC encoded data using a “product code.” A product code may be derived from component codes by arranging the information to be encoded into a two-dimensional array. A component code is assigned to each dimension and applied to all vectors in the assigned dimension. The component codes can be different or the same for each dimension. The encoded information results in an n1×n2 array. Information symbols are loaded into a k1×k2 portion of the n1×n2 array. For example, C1 and C2 are linear block codes with parameters [n1, k1, d1] and [n2, k2, d2] respectively. The information symbols to be encoded by C1 and C2 in this example may be binary data. The first parameter n denotes the code word length or number of coded bits. The second parameter k denotes the dimension of the code and corresponds to the number of information bits to be encoded. The third parameter d denotes the minimum Hamming distance of the code or the minimum number of positions in which two distinct code words must differ. Generally, r=n−k check symbols result from encoding the k information symbols. The two-dimensional product code C1{circle around (×)} C2 is formed by applying C1 to each of the columns and C2 to each of the rows of the k1×k2 rectangular array of information bits as depicted in FIG. 1. Thus, the each code word in C1{circle around (×)} C2 can be represented as an n1×n2 matrix, whose columns are code words in C1 and whose rows are code words in C2. The product code has parameters [n1n2, k1k2, d1d2]. Alternatively, C2 may first be applied to the rows and then C1 to the columns. The order that codes are applied does not matter. In either case the check on checks will be the same because the codes are linear block codes.
Product codes may be decoded in an iterative fashion using decoders corresponding to the component codes. For example, in a two-dimensional product code, one could first apply a hard-decision decoder for C1 to the columns, and then apply a hard-decision decoder for C2 to the rows as corrected by the column-decoding pass. Often, error patterns that were uncorrectable in a given row during the first row-decoding pass become correctable after the column-decoding pass has corrected some errors. Thus, iterating between row-decoding and column-decoding may correct more errors than a single decoding pass. A fixed number of iterations may be performed. Alternatively, iterations may be preformed until some stopping criterion is satisfied, for example, performing iterative decoding until the decoded array passes a cyclic redundancy check. Also, product codes may be decoded using turbo decoding techniques that provide an efficient method of exchanging soft-decision information among component decoders. For more information on turbo decoding see: Pyndia, R. M., Near-Optimum Decoding of Product Codes: Block Turbo Codes, IEEE Tans. on Communications, Vol. 46, No. 8, August 1998, pp. 1003-1010. Because a code may be decoded using various methods, the names used for codes will refer exclusively to their construction and not to a decoding method.
Bose-Chaudhuri-Hocquenghem (BCH) codes are frequently used in the construction of product codes because the class offers a wide choice of block sizes and rates while resulting in efficient decoders. Reed-Solomon codes are non-binary cyclic codes constructed in the analogous fashion over the Galois field GF(2r) and are similarly well-suited for non-binary product code constructions. BCH and Reed-Solomon codes are briefly described below.
A BCH code of natural length n=2r−1 is a binary cyclic code in which the generator polynomial g(x) has binary coefficients and has the elements αb, αb+1, . . . , αb+d−2 in the finite field GF(2r) as roots. Here b and d are design parameters, and α is a primitive in GF(2r). The generator polynomial for this code is:g(x)=LCM(Mb(x),Mb+1(x), . . . ,Mb+d−2(x)).  (1)Mi(x) denotes the minimal polynomial for the element αi. This class of BCH codes is referred to as the class of primitive BCH codes. If b=1, the codes are further classified as narrowsense primitive BCH codes. More generally, we can let α be a non-primitive element in GF(2r) of multiplicative order ord α. In this case, the BCH codes so constructed have natural length n=ord α and are referred to as non-primitive BCH codes. In all cases, the minimum Hamming distance of the BCH code is at least as large as the design parameter d. The maximum guaranteed error correction capability of the code is therefore at least t=[(d−1)/2]. The dimension of the code is k=n−deg g(x).
Reed-Solomon codes are non-binary cyclic codes constructed in the analogous fashion over the Galois field GF(2r) and are similarly well-suited for non-binary product code constructions. The non-binary generator polynomialg(x)=(x+αb)(x+αb+1) . . . (x+αb+d−2)  (2)generates a non-binary Reed-Solomon code of length n=ord α and minimum Hamming distance of exactly d. Usually, α is taken to be primitive so that n=2r−1. The dimension of the code is k=n−deg g(x)=n−d+1.
A cyclic code of length n consists of all polynomials of degree <n that are proper multiples of the generator polynomial g(x). Thus, cyclic codes are nested in the following sense. Let C1, C2, . . . , CL be a family of cyclic codes in which code Ci has generator polynomial gi(x). Then all of the codes Ci are contained in the cyclic code Csup as subcodes, where Csup has generator polynomial:g(x)=GCD(g1(x),g2(x), . . . , gL(x)).  (3)GCD refers to the greatest common divisor. For example, among the narrowsense primitive BCH codes, the code with maximum error-correcting capability t=1 contains the code with maximum error-correcting capability t=2, which contains the code with maximum error-correcting capability t=3, and so forth. This nesting property of the BCH (and Reed-Solomon codes) plays no significant role in product code constructions, but nesting is a useful feature in the irregular array code construction of the present invention.
One problem with product codes is that they do not have a “thin spectrum” in the sense that the number of code words of minimum Hamming weight dmin, weight dmin+1, etc. are small. Product codes do not have a thin spectrum. For example, the product code generated by the single parity check code. The single parity check code has dmin=2, so the product code has dmin=4. All patterns of the following form are code words of weight 4:C(M,N)=C(M,N+n)=C(M+m,N)=C(M+n,N+n)=1,C(i,j)=0 for all other i,j. In fact, any translation or expansion of a valid pattern of 1s (i.e. valid meaning that the result is a codeword) is also a valid pattern. This is due to the regularity of the product code.
Assuming the optimal decoder, the asymptotic high signal to noise ratio performance of a code in an additive white Guassian noise like channel is governed by the minimum Hamming weight and number of code words of minimum Hamming weight. At low SNR, the entire weight spectrum is important, so spectral thinness results in better performance for SNRs near the Shannon limit. Therefore there remains a need for FEC codes that improve performance at lower SNRs found in many applications.